// https://www.lintcode.com/problem/number-of-airplanes-in-the-sky/description

/**
 * Definition of Interval:
 * classs Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this->start = start;
 *         this->end = end;
 *     }
 * }
 */

// map，不用额外排序
int countOfAirplanes(vector<Interval> &airplanes) {
    map<int, int> rec;
    for (auto& a: airplanes) {
        rec[a.start]++;
        rec[a.end]--;
    }
    int max_val = 0;
    int sum = 0;
    for (auto& r: rec) {
        sum += r.second;
        max_val = max(sum, max_val);
    }
    return max_val;
}

// 扫描线标准写法
// 排序O(nlogn)，扫描O(n)
class Event {
public:
    int val;
    // bool flag; 注意不能用bool，不然直接加flag，-1也是1
    int flag;
    Event(int val, int flag) {
        this->val = val;
        this->flag = flag;
    }
    bool operator < (const Event& e) const {
        return this->val < e.val || (this->val == e.val && this->flag < e.flag); //主要是看冲突的要不要记录，降落了空中就没有了
    }
};

class Solution {
public:
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    int countOfAirplanes(vector<Interval> &airplanes) {
        vector<Event> rec;
        for (auto& a: airplanes) {
            rec.push_back(Event(a.start, 1));
            rec.push_back(Event(a.end, -1));
        }
        sort(rec.begin(), rec.end());
        int max_val = 0;
        int cnt = 0;
        for (auto& e: rec) {
            cnt += e.flag;    
            max_val = max(max_val, cnt);      
        }
        return max_val;
    }
};

// 法二：贪心+最小堆
class Solution {
public:
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    static bool cmp(Interval& i1, Interval& i2) {
        return i1.start < i2.start || (i1.start == i2.start && i1.end < i2.end);
    }
    int countOfAirplanes(vector<Interval> &airplanes) {
        priority_queue<int, vector<int>, greater<int>> q;
        sort(airplanes.begin(), airplanes.end(), cmp);
        int max_val = 0;
        for (auto& a: airplanes) {
            q.push(a.end); //先push，就不用判断q是否为空了
            // if (a.start > q.top()) {
            if (a.start >= q.top()) {
                q.pop();
            }
            max_val = max(max_val, (int)q.size());
        }
        return max_val;
    }
};

// better
class Solution {
public:
    /**
     * @param airplanes: An interval array
     * @return: Count of airplanes are in the sky.
     */
    bool static cmp(Interval& a, Interval& b) {
        return a.start < b.start || (a.start == b.start && a.end < b.end);
    }
    int countOfAirplanes(vector<Interval> &airplanes) {
        if (airplanes.empty()) return 0;
        priority_queue<int, vector<int>, greater<int>> q;
        sort(airplanes.begin(), airplanes.end(), cmp);
        q.push(airplanes[0].end);
        for (int i = 1; i < airplanes.size(); ++i) {
            if (airplanes[i].start >= q.top()) {
                q.pop();
            }
            q.push(airplanes[i].end);
        }
        return q.size();
    }
};